package 集合.stack;

import java.util.Deque;
import java.util.ArrayDeque;
import java.util.LinkedList;
import java.util.Map;
import java.util.Stack;
/*
//利用Stack把一个给定的整数转换为十六进制：
public class 使用stack {
	public static void main(String[] args) {
		String hex = toHex(12500);
		if (hex.equalsIgnoreCase("30D4")) {
			System.out.println("测试通过");
		} else {
			System.out.println("测试失败");
		}
	}

	static String toHex(int n) {
	  Deque<Integer> stack = new ArrayDeque<>();//ArrayDeque实现Deque接口
//	  Deque<Integer> stack = new LinkedList<>();//LinkedList实现Deque接口
//	  Stack<Integer> stack = new Stack<>();//Stack继承自Vecter类
		StringBuilder s1 = new StringBuilder();
		while (n % 16 != 0 || n / 16 != 0) {
			stack.push(n % 16);
			n = n / 16;
		}
		while (!stack.isEmpty()) {
			int s2 = stack.pop();
			if (s2 > 9) {
				switch (s2) {
				case 10:
					s1.append("A");
					break;
				case 11:
					s1.append("B");
					break;
				case 12:
					s1.append("C");
					break;
				case 13:
					s1.append("D");
					break;
				case 14:
					s1.append("E");
					break;
				case 15:
				s1.append("F");
				}
			} else {
				s1.append(Integer.toString(s2));
			}
		}
		return s1.toString();
	}
}
*/
//把带变量的中缀表达式编译为后缀表达式，执行后缀表达式时，传入变量的值并获得计算结果：
//计算中缀表达式 --> 后缀表达式 即如：1 + 2 * (9 - 5)  --> 1 2 9 5 - * +
//在编写程序的时候，我们使用的带括号的数学表达式实际上是中缀表达式，即运算符在中间，例如：1 + 2 * (9 - 5)。
//但是计算机执行表达式的时候，它并不能直接计算中缀表达式，而是通过编译器把中缀表达式转换为后缀表达式，例如：1 2 9 5 - * +。
/*
计算后缀表达式不考虑优先级，直接从左到右依次计算，因此计算起来简单。首先准备一个空的栈：

│   │
│   │
│   │
│   │
│   │
│   │
│   │
│   │
└───┘
然后我们依次扫描后缀表达式1 2 9 5 - * +，遇到数字1，就直接扔到栈里：

│   │
│   │
│   │
│   │
│   │
│   │
│   │
│ 1 │
└───┘
紧接着，遇到数字2，9，5，也扔到栈里：

│   │
│ 5 │
│   │
│ 9 │
│   │
│ 2 │
│   │
│ 1 │
└───┘
接下来遇到减号时，弹出栈顶的两个元素，并计算9-5=4，把结果4压栈：

│   │
│   │
│   │
│ 4 │
│   │
│ 2 │
│   │
│ 1 │
└───┘
接下来遇到*号时，弹出栈顶的两个元素，并计算2*4=8，把结果8压栈：

│   │
│   │
│   │
│   │
│   │
│ 8 │
│   │
│ 1 │
└───┘
接下来遇到+号时，弹出栈顶的两个元素，并计算1+8=9，把结果9压栈：

│   │
│   │
│   │
│   │
│   │
│   │
│   │
│ 9 │
└───┘
扫描结束后，没有更多的计算了，弹出栈的唯一一个元素，得到计算结果9。*/
public class 使用stack {
	public static void main(String[] args) {
		String exp = "x + 2 * (y - 5)";
		SuffixExpression se = compile(exp);
		Map<String, Integer> env = Map.of("x", 1, "y", 9);
		int result = se.execute(env);
		System.out.println(env);
		System.out.println(exp + " = " + result + " " + (result == 1 + 2 * (9 - 5) ? "yes" : "no"));
	}
	static SuffixExpression compile(String exp) {
		// TODO:
		Deque<String> nums = new LinkedList<>();
    	Deque<String> symbols = new LinkedList<>();
    	for (int i = 0; i < exp.length(); i++) {
			String n = exp.charAt(i) + "";
			if (n.equals(" ") || n.equals("(") || n.equals(")")) continue; 
			if (n.equals("+") || n.equals("-") || n.equals("*") || n.equals("/")) {
				symbols.push(n);
				continue;
			}
			nums.push(n);
		}
      return new SuffixExpression(nums, symbols);
	}
}

class SuffixExpression {
	Deque<String> nums;
	Deque<String> symbols;
	public SuffixExpression(Deque<String> nums, Deque<String> symbols) {
		this.nums = nums;
		this.symbols = symbols;
	}
	int execute(Map<String, Integer> env) {
		int res = 0;
		while (symbols.size() != 0) {
			String last = nums.pop();
			String pre = nums.pop();
			String symb = (String) symbols.pop();
			int lastV = env.get(last) == null ? Integer.parseInt(last): env.get(last);
			int preV = env.get(pre) == null ? Integer.parseInt(pre): env.get(pre);
			switch(symb) {
			case "+": 
				res = preV + lastV;
				break;
			case "-": 
				res = preV - lastV;
				break;
			case "*": 
				res = preV * lastV;
				break;
			case "/": 
				res = preV / lastV;
				break;
			}
			nums.push(res + "");
		}
		return res;
	}
}



/*
Java中用Deque接口代替Stack接口完成栈功能

之前在有需要用到栈功能的时候，都是通过使用Stack接口完成的，也就是：
Stack <T> stack = new Stack <>（）
​
但今天突然发现，Java Doc里建议用Deque替代Stack接口完成栈的功能，于是我稍微研究了一下。

Java文档在JavaDoc for Stack中这样说：
Deque接口及其实现提供了一组更完整和一致的LIFO堆栈操作，应优先使用此类。
例如：Deque<Integer> stack = new ArrayDeque<Integer>();

然后在JavaDoc for Deque中这样说：
双端队列也可以用作LIFO（后进先出）堆栈。此接口应优先于旧版Stack类使用。当双端队列用作堆栈时，元素从双端队列的开头被压入并弹出。
大概意思就是让我们不要再使用Stack接口去完成栈的功能，而是使用Deque，并提供了相关示例。

原因
那么为什么要这么做呢？首先，我们可以发现deque的是继承自队列，而栈是继承自向量，这就比较奇怪了。
矢量是由数组实现的集合类，他包含了大量集合处理的方法。而Stack之所以继承Vector，是为了补充Vector中的方法，来实现进栈（push），出栈（pop）等操作。这里就是Stack设计不好的地方，既然只是为了实现栈，不用链表来单独该堆栈在基于实现实现上效率纠正的堆栈，另外因为继承矢量类，堆栈可以替换向量大量方法，这使得Stack在设计上不严谨，例如Vector中的：

public void add（int index，E element）{ insertElementAt(element，index); 
}
可以在指定位置添加元素，这与Stack的设计理念相冲突。

【Deque】
Java中的Deuqe，即“双端队列”的缩写，是Java中的双端串联集合类型，它集成了自定队列，完全具有普通的FIFO的功能，同时它也具有堆栈的LIFO功能，并且保留了推弹出状语从句函数，所以使用起来应该是一点障碍都没有。
deque的可以由ArrayDeuqe或者LinkedList的实现，它们两者使用的区别以及优劣也就是数组和链表的区别，你懂得。

【ArrayDeque】
​ArrayDeque没有容量限制，可根据需求自动进行扩容。ArrayDeque可以作为栈来使用，效率要高于堆栈。ArrayDeque也可以作为一种来使用，效率相较于基于双向链表的LinkedList也要更好一些。注意，ArrayDeque不支持为null的元素。

【LinkedList】
LinkedList与ArrayList一样实现List接口，只是ArrayList是List接口的大小可变数组的实现，LinkedList是List接口链表的实现。比ArrayList的逊色些。
　　链表实现所有可选的列表操作，并允许所有的元素包括空。
　　除了实现列表接口外，LinkedList的类还为在列表的开头及结尾得到，删除和插入元素提供了统一的命名方法这些操作允许将链接列表替换为可用的、、或双端的。这样的
　　实现Deque接口，为添加，轮询提供先进先出操作，以及其他方式和双端操作。
　　所有操作都是按照双重链接进行的。列表的需要执行的。在列表中编索引的操作初始化开头或结尾遍历列表（从靠近指定索引的一端）。
　　同时，与ArrayList一样此实现不是同步的。

总结
决定以后在Java中要用到栈的话，再也不用Stack了，弃暗透明，转向Deque！*/